package com.samxcode.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * Given a string, find the length of the longest substring without repeating characters. For
 * example, the longest substring without repeating letters for "abcabcbb" is "abc", which the
 * length is 3. For "bbbbb" the longest substring is "b", with the length of 1.
 * 
 * solution:
 * 
 * A boolean array is used to save the occurrence of characters. We move one pointer forward, and
 * check the boolean array. If it is false, we turn it to true. If it’s true, we need to keep moving
 * another pointer forward until it meets the same character as the first pointer pointing to. We
 * can update the max value every time if we move the first pointer.
 * 
 * reference:
 * http://www.lifeincode.net/programming/leetcode-longest-substring-without-repeating-characters/
 * 
 * @author Sam
 *
 */
public class LongestSubstring {

    public static void main(String[] args) {
        int i = lengthOfLongestSubstring("a");
        System.out.println(i);
    }


    public static int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        int max = 0;
        int start = 0;
        for (int i = 1; i <= s.length(); i++) {
            Character c = s.charAt(i - 1);
            Integer preIndex = map.get(c);
            // 起始位置小于该元素上一次出现位置，更新
            if (preIndex != null && start < preIndex) {
                start = preIndex;
            }
            if (max < (i - start)) {
                max = i - start;
            }
            map.put(c, i);
        }
        return max;
    }


    public static int lengthOfLongestSubstring2(String s) {
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        int max = 0;
        int start = 0;
        int length = s.length();
        for (int i = 0; i < length; i++) {
            Character c = s.charAt(i);
            Integer preIndex = map.get(c);
            if (preIndex != null && start <= preIndex) {
                if (max < (i - start)) {
                    max = i - start;
                }
                start = preIndex + 1;
            }
            map.put(c, i);
        }
        if (max < length - start) {
            max = length - start;
        }
        return max;
    }


    public static int lengthOfLongestSubstring3(String s) {
        int length = s.length();
        if (length == 0) {
            return 0;
        }
        int start = 0;
        boolean[] letters = new boolean[256];
        int max = 0;
        letters[s.charAt(0)] = true;
        for (int i = 1; i < length; i++) {
            if (!letters[s.charAt(i)])
                letters[s.charAt(i)] = true;
            else {
                if (max < i - start) {
                    max = i - start;
                }
                while (s.charAt(start) != s.charAt(i)) {
                    letters[s.charAt(start)] = false;
                    start++;
                }
                start++;
            }
        }
        if (max < length - start) {
            max = length - start;
        }
        return max;
    }
}
